﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
//编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/insert-into-bits-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int insertBits(int N, int M, int i, int j){
//	for (int k = i; k <= j; k++)
//	{
//		N &= ~((unsigned int)1 << k);
//	}
//	N |= (M << i);
//	return N;
//}







//给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
//int reverseBits(int num){
//	int max = 0;
//	int count = 0;
//	int c = 0;
//	for (int i = 0; i<32; i++)
//	{
//		if (num & 1)
//		{
//			count++;
//		}
//		else
//		{
//			if (count + c + 1>max)
//			{
//				max = count + c + 1;
//			}
//			c = count;
//			count = 0;
//		}
//		num >>= 1;
//	}
//	if (count + c + 1>max)
//	{
//		max = count + c + 1;
//	}
//	(max>32) && (max = 32);
//	return max;
//}






//三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/three-steps-problem-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int waysToStep(int n){
//	if (n<4)
//	{
//		return n == 3 ? 4 : n;
//	}
//	int a = 1;
//	int b = 2;
//	int c = 4;
//	int tmp = 0;
//	for (int i = 4; i <= n; i++)
//	{
//		tmp = (a + b) % 1000000007 + c;
//		a = b;
//		b = c;
//		c = tmp % 1000000007;
//	}
//	return c;
//}









//魔术索引。 在数组A[0...n - 1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回 - 1。若有多个魔术索引，返回索引值最小的一个。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/magic-index-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int findMagicIndex(int* nums, int numsSize){
//	for (int i = 0; i<numsSize; i++)
//	{
//		if (nums[i] == i)
//		{
//			return i;
//		}
//	}
//	return -1;
//}







//整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
//int convertInteger(int A, int B){
//	unsigned int c = A^B;
//	int count = 0;
//	while (c)
//	{
//		count++;
//		c = c&(c - 1);
//	}
//	return count;
//}








//给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
//初始化 A 和 B 的元素数量分别为 m 和 n。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/sorted-merge-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int cmp(int* a, int* b)
//{
//	return *a - *b;
//}
//void merge(int* A, int ASize, int m, int* B, int BSize, int n){
//	for (int i = 0; i != n; i++)
//	{
//		A[i + m] = B[i];
//	}
//	return qsort(A, ASize, sizeof(int), cmp);
//}







//稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
//int findString(char** words, int wordsSize, char* s){
//	int i = 0;
//	for (i = 0; i<wordsSize; i++)
//	{
//		if (strcmp(words[i], s) == 0)
//		{
//			return i;
//		}
//	}
//	return -1;
//}








//设计一个算法，算出 n 阶乘有多少个尾随零。
//int trailingZeroes(int n){
//	int count = 0;
//	while (n)
//	{
//		n /= 5;
//		count += n;
//	}
//	return count;
//}









/**你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diving-board-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* divingBoard(int shorter, int longer, int k, int* returnSize){
//	if (k == 0)
//	{
//		*returnSize = 0;
//		return NULL;
//	}
//	if (shorter == longer)
//	{
//		int* a = (int*)malloc(sizeof(int));
//		*returnSize = 1;
//		*a = shorter*k;
//		return a;
//	}
//	int* a = (int*)malloc(sizeof(int)*(k + 1));
//	*returnSize = k + 1;
//	for (int i = 0; i <= k; i++)
//	{
//		a[i] = shorter*(k - i) + longer*i;
//	}
//	return a;
//}









//给定一个整数数组，找出总和最大的连续数列，并返回总和。
//int maxSubArray(int* nums, int numsSize){
//	int max = 0;
//	int i = 0;
//	for (i = 1; i<numsSize; i++)
//	{
//		nums[i] += fmax(0, nums[i - 1]);
//	}
//	max = nums[0];
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i]>max)
//		{
//			max = nums[i];
//		}
//	}
//	return max;
//}







//设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
//int add(int a, int b){
//	unsigned int c = a^b;
//	unsigned int d = a&b;
//	while (d)
//	{
//		a = c;
//		b = d << 1;
//		c = a^b;
//		d = a&b;
//	}
//	return c;
//}







//数组nums包含从0到n的所有整数，但其中缺了一个。
//请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//int missingNumber(int* nums, int numsSize){
//	int i = 0;
//	int min = 0;
//	int max = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		min += nums[i];
//		max += numsSize - i;
//	}
//	return max - min;
//}







//数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回 - 1。
//int majorityElement(int* nums, int numsSize){
//	int count = 1;
//	int num = nums[0];
//	for (int i = 1; i<numsSize; i++)
//	{
//		if (nums[i] == num)
//		{
//			count++;
//			continue;
//		}
//		else if (--count == 0)
//		{
//			count = 1;
//			num = nums[i];
//		}
//	}
//	if (count>numsSize / 2)
//	{
//		return num;
//	}
//	count = 0;
//	for (int i = 0; i<numsSize; i++)
//	{
//		if (nums[i] == num)
//		{
//			count++;
//		}
//	}
//	if (count>numsSize / 2)
//	{
//		return num;
//	}
//	return -1;
//}








//一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/the-masseuse-lcci
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int massage(int* nums, int numsSize){
//	if (numsSize == 0)
//	{
//		return 0;
//	}
//	if (numsSize == 1)
//	{
//		return nums[0];
//	}
//	nums[1] = nums[0]>nums[1] ? nums[0] : nums[1];
//	for (int i = 2; i<numsSize; i++)
//	{
//		nums[i] = nums[i - 1]>nums[i - 2] + nums[i] ? nums[i - 1] : nums[i - 2] + nums[i];
//	}
//	return nums[numsSize - 1];
//}






/**珠玑妙算游戏（the game of master mind）的玩法如下。

计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。

给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/master-mind-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* masterMind(char* solution, char* guess, int* returnSize){
//	int* a = (int*)malloc(sizeof(int) * 2);
//	a[0] = 0;
//	a[1] = 0;
//	*returnSize = 2;
//	int i = 0, rs = 0, ys = 0, gs = 0, bs = 0, rg = 0, yg = 0, Gg = 0, bg = 0;
//	for (i = 0; i<4; i++)
//	{
//		if (solution[i] == guess[i])
//		{
//			a[0]++;
//		}
//	}
//	for (i = 0; i<4; i++)
//	{
//		if (solution[i] == 'R')
//		{
//			rs++;
//		}
//		else if (solution[i] == 'Y')
//		{
//			ys++;
//		}
//		else if (solution[i] == 'G')
//		{
//			gs++;
//		}
//		else if (solution[i] == 'B')
//		{
//			bs++;
//		}
//	}
//	for (i = 0; i<4; i++)
//	{
//		if (guess[i] == 'R')
//		{
//			rg++;
//		}
//		else if (guess[i] == 'Y')
//		{
//			yg++;
//		}
//		else if (guess[i] == 'G')
//		{
//			Gg++;
//		}
//		else if (guess[i] == 'B')
//		{
//			bg++;
//		}
//	}
//	int count = fmin(rs, rg) + fmin(ys, yg) + fmin(gs, Gg) + fmin(bg, bs);
//	a[1] = count - a[0];
//	return a;
//}